import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: user
 * Date: 2024-04-13
 * Time: 15:31
 */
public class Test {
                     // 力扣：144：二叉树非递归前序排列
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        Stack<TreeNode> s = new Stack<>();
//        if(root == null){
//            return list;
//        }
//        TreeNode cur = root;
//        while(cur != null||!s.isEmpty() ) {
//            while(cur != null){
//                s.push(cur);
//                list.add(cur.val);
//                cur = cur.left;
//            }
//            TreeNode t = s.pop();
//            cur = t.right;
//        }
//        return list;
//    }
                  //力扣：94. 1，二叉树的中序非递归遍历
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> ay = new ArrayList<>();
//        Stack<TreeNode> stack = new Stack<>();
//        if(root == null){
//            return ay;
//        }
//        TreeNode cur = root;
//        while(cur != null||!stack.isEmpty()){
//            while(cur != null){
//                stack.push(cur);
//                cur = cur.left;
//            }
//            TreeNode top = stack.pop();
//            ay.add(top.val);
//            cur = top.right;
//        }
//        return ay;
//    }
                       //2.递归
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> ay = new ArrayList<>();
//        inOrder(root,ay);
//        return ay;
//    }
//    public static  void inOrder(TreeNode root,List<Integer> ay){
//        if(root == null){
//            return ;
//        }
//        inOrder(root.left,ay);
//        ay.add(root.val);
//        inOrder(root.right,ay);
//    }
                //力扣：145. 二叉树的后序遍历
                //  递归
//         public List<Integer> postorderTraversal(TreeNode root) {
//          List<Integer> pt = new ArrayList<>();
//            postOrder(root,pt);
//            return pt;
//          }
//    public void postOrder(TreeNode root,List<Integer> pt){
//        if(root == null){
//            return;
//        }
//        postOrder(root.left,pt);
//        postOrder(root.right,pt);
//        pt.add(root.val);
//    }
                //非递归
//                     public List<Integer> postorderTraversal(TreeNode root) {
//                         List<Integer> pt = new ArrayList<>();
//                         Stack<TreeNode> stack = new Stack<>();
//                        if(root == null){
//                             return pt;
//                         }
//                         TreeNode cur = root;
//                         TreeNode flg = null;
//                         while(cur != null||!stack.isEmpty()){
//                             while(cur != null){
//                                 stack.push(cur);
//                                 cur = cur.left;
//                             }
//                             TreeNode top = stack.peek();
//                             if(top.right == null||top.right == flg){
//                                 stack.pop();
//                                 pt.add(top.val);
//                                 flg = top;
//                             }
//                             else{
//                                 cur = top.right;
//                             }
//
//                         }
//                         return pt;
//                     }
//                   }

                //力扣：236. 二叉树的最近公共祖先
//    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
//        if(root == null){
//            return null;
//        }
//        if(root == p){
//            return p;
//        }
//        if(root == q){
//            return q;
//        }
//        TreeNode findL = lowestCommonAncestor(root.left,p,q);
//        TreeNode findR = lowestCommonAncestor(root.right,p,q);
//        if(findL == null){
//            return findR;
//        }
//        else if(findR == null){
//            return findL;
//        }
//        else{
//            return root;
//        }
    //}
                       //力扣：102：二叉树的程序遍历
//                public List<List<Integer>> levelOrder(TreeNode root) {
//                    List<List<Integer>> ret = new ArrayList<>();
//                    if(root == null){
//                        return ret;
//                    }
//
//                    Queue<TreeNode> queue = new LinkedList<>();
//                    queue.offer(root);
//                    while(!queue.isEmpty()){
//                        int size = queue.size();
//                        List<Integer> level = new ArrayList<>();
//                        while(size != 0){
//
//                            TreeNode cur = queue.poll();
//                            level.add(cur.val);
//                            if(cur.left != null){
//                                queue.offer(cur.left);
//                            }
//                            if(cur.right != null){
//                                queue.offer(cur.right);
//                            }
//                            size--;
//                        }
//                        ret.add(level);
//
//                    }
//                    return ret;
//                }
    //力扣：107.二叉树的程序遍历2:自底向上的层序遍历
//                public List<List<Integer>> levelOrderBottom(TreeNode root) {
//
//                    List<List<Integer>> ret = new ArrayList<>();
//                    Stack<List<Integer>> stack = new Stack<>();
//                    if(root == null){
//                        return ret;
//                    }
//
//                    Queue<TreeNode> queue = new LinkedList<>();
//                    queue.offer(root);
//                    while(!queue.isEmpty()){
//                        int size = queue.size();
//                        List<Integer> level = new ArrayList<>();
//                        while(size != 0){
//
//                            TreeNode cur = queue.poll();
//                            level.add(cur.val);
//                            if(cur.left != null){
//                                queue.offer(cur.left);
//                            }
//                            if(cur.right != null){
//                                queue.offer(cur.right);
//                            }
//                            size--;
//                        }
//                        stack.push(level);
//
//                    }
//                    while(!stack.isEmpty()){
//                        ret.add(stack.pop());
//                    }
//                    return ret;
//
//                }
            //力扣：606. 根据二叉树创建字符串
//                public String tree2str(TreeNode root) {
//                   StringBuilder stringbuilder = new StringBuilder();
//                   tree2strChild(root,stringbuilder);
//                   return stringbuilder.toString();
//                }
//   public void tree2strChild(TreeNode root,StringBuilder stringbuilder){
//      if(root == null){
//         return;
//      }
//
//      stringbuilder.append(root.val);
//
//
//      if(root.left != null ){
//         stringbuilder.append( "(" );
//         tree2strChild(root.left,stringbuilder);
//         stringbuilder.append(")");
//      }
//      else{
//         if(root.right == null){
//            return;
//
//         }
//         else{
//            stringbuilder.append("()");
//         }
//      }
//      if(root.right == null) {
//         return;
//      }else {
//         stringbuilder.append("(");
//         tree2strChild(root.right,stringbuilder);
//         stringbuilder.append(")");
//      }
//   }
   //

             //力扣：105. 从前序与中序遍历序列构造二叉树
//             public int preorderindex = 0;
//   public TreeNode buildTree(int[] preorder, int[] inorder) {
//      return buildTreeChild(preorder,inorder,0,(inorder.length - 1));
//   }
//   public TreeNode buildTreeChild(int[] preorder, int[] inorder,int start,int end){
//      if(start > end){
//         return null;
//      }
//      TreeNode root = new TreeNode(preorder[preorderindex]);
//      int rootindex = findIndex(inorder,preorder[preorderindex],start,end);
//      preorderindex++;
//      root.left = buildTreeChild(preorder,inorder,start,rootindex - 1);
//      root.right = buildTreeChild(preorder,inorder,rootindex + 1,end);
//      return root;
//   }
//   public int findIndex(int[] inorder,int key,int start,int end){
//      for(int i = start;i <= end; i++){
//         if(key == inorder[i]){
//            return i;
//         }
//      }
//      return -1;
//   }
                      //力扣：106. 从中序与后序遍历序列构造二叉树
//             public int postindex = 0;
//   public TreeNode buildTree(int[] inorder, int[] postorder) {
//      postindex = postorder.length -1;
//      return buildTreeChild( inorder, postorder,0, inorder.length - 1 );
//
//   }
//   public TreeNode buildTreeChild(int[] inorder, int[] postorder,int start,int end){
//      if(start > end){
//         return null;
//      }
//      TreeNode root = new TreeNode(postorder[postindex]);
//      int rootindex = findInorder(inorder,postorder[postindex],start,end);
//      postindex--;
//      root.right = buildTreeChild( inorder, postorder,rootindex+1,end );
//      root.left = buildTreeChild( inorder, postorder,start,rootindex - 1 );
//
//      return root;
//
//   }
//   public int findInorder(int[] inorder,int key,int start,int end){
//
//      int cur = start;
//      while(cur <= end){
//         if(key == inorder[cur]){
//            return cur;
//         }
//         cur++;
//      }
//      return -1;
//   }
   }